package dp.simple;

/**
 * 爬楼梯
 * Example 1:
 *
 * Input: n = 2
 * Output: 2
 * Explanation: There are two ways to climb to the top.
 * 1. 1 step + 1 step
 * 2. 2 steps
 * Example 2:
 *
 * Input: n = 3
 * Output: 3
 * Explanation: There are three ways to climb to the top.
 * 1. 1 step + 1 step + 1 step
 * 2. 1 step + 2 steps
 * 3. 2 steps + 1 step
 *
 * 链接：https://leetcode-cn.com/problems/climbing-stairs
 */
public class ClimbingStairs_70 {

    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int a = 1, b = 2;
        int sum = a + b;
        int i = 3;
        while(i < n) {
            a = b;
            b = sum;
            sum = a + b;
            i++;
        }
        return sum;
    }
}
